Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution:

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * class RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode next, random;
  6.  *     RandomListNode(int x) { this.label = x; }
  7.  * };
  8.  */
  9. public class Solution {
  10.   public RandomListNode copyRandomList(RandomListNode head) {
  11.     if (head == null) return null;
  13.     Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
  15.     // step 1. copy all the nodes
  16.     RandomListNode node = head;
  17.     while (node != null) {
  18.       map.put(node, new RandomListNode(node.label));
  19.       node = node.next;
  20.     }
  22.     // step 2. assign next and random pointers
  23.     node = head;
  24.     while (node != null) {
  25.       map.get(node).next = map.get(node.next);
  26.       map.get(node).random = map.get(node.random);
  27.       node = node.next;
  28.     }
  30.     return map.get(head);
  31.   }
  32. }